
/* domain
	Dom_Nill = Nill &
        Dom_Cons = Cons &
        Dom_Snoc = Cons &
        Dom_Cons \Un Dom_Nill = Lst &
        Dom_Cons \Int Dom_Nill = empty 
*/
  
 
sealed abstract class Lst
class Cons(val head: Elem, val tail: Lst) extends Lst
class Nill extends Lst

class Elem

object Nill {
  def apply(): Nill = new Nill()
  def unapply(n: Nill): Boolean = true
}

object Cons {
  def apply(head: Elem, tail: Lst): Cons = 
    new Cons(head,tail)
    
  def unapply(c: Cons): Option[(Elem,Lst)] = 
    Some(Tuple2(c.head,c.tail))
}


/**
object Snoc {
  def unapply(c: Lst): Option[(Lst,Elem)] = (c : Lst) match {
    case Nill() => None
    case Cons(c : Elem, xs: Lst) => (xs : Lst) match {
      case Nill() => Some(Tuple2(Nill(),c))
      case Snoc(ys: Lst, y: Elem) => Some(Tuple2(Cons(c,ys),y))
    }
  }
}
*/

object Snoc {
  def unapply(c: Cons): Option[(Lst,Elem)] = (c : Cons) match {
    case Cons(c : Elem, xs: Lst) => (xs : Lst) match {
      case Nill() => Some(Tuple2(Nill(),c))
      case Snoc(ys: Lst, y: Elem) => Some(Tuple2(Cons(c,ys),y))
    }
  }
}



object Test {
  
  def firstAndLast(lst: Lst): Lst = (lst: Lst) match {
    case Nill()                         => lst
    case Cons(x: Elem, Nill())          => lst
    case Cons(x: Elem, Snoc(_,y: Elem)) => Cons(x,Cons(y,Nill()))
  }
}